package com.gwcloud.leetcode.tags.dp;

/** 
* @ClassName   : Leetcode0199 
* @author      : ganwei 
* @date        : 2020年5月17日 
* @Description : 188. 买卖股票的最佳时机 IV 
*/
public class Leetcode0188 {
    public int maxProfit(int k, int[] prices) {
    	int n = prices.length;
    	if(k >= n/2) {
    		return maxProfitWithInf(prices);
    	}

    	int[][][] dp = new int[n][k+1][2];
    	
    	for(int i = 0; i < n; i++){
    		dp[i][0][0] = 0;
    		dp[i][0][1] = Integer.MIN_VALUE;
    	}
    	
    	for(int i = 0; i < n; i++) {
    		for(int j = k; j >= 1; j--) {
    			if(i-1 == -1) {
        			dp[i][j][0] = 0;
        			dp[i][j][1] = 0 - prices[i];
    				continue;
    			}
    			dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
    			dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
    		}
    	}
    	
    	return dp[n-1][k][0];
    }
    
    /**
     * -n个数的最大操作
     */
	public int maxProfitWithInf(int[] prices) {
        int n = prices.length;
        int d_i_0 = 0;
        int d_i_1 = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
        	int temp = d_i_0;
        	d_i_0 = Math.max(d_i_0, d_i_1 + prices[i]);
        	d_i_1 = Math.max(d_i_1, temp - prices[i]);
        }
        
		return d_i_0;
    }
    public static void main(String[] args) {
    	Leetcode0188 l0188 = new Leetcode0188();
    	int[] prices = {1,2,4,2,5,7,2,4,9,0};
    	System.out.println(l0188.maxProfit(2, prices));
    	
    }
}
